/*
2021-10-17
https://leetcode-cn.com/problems/second-minimum-time-to-reach-destination/
*/ 
const int N=1e4+5,M=4*N;
typedef pair<int,int> PII;


class Solution {
public:
    int h[N],e[M],ne[M],idx;
    int dist[N],ans,cnt[N];

    void add(int a,int b)
    {
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }

    void bfs(int n)
            {
                ans=0;
                memset(dist,0x3f,sizeof dist);
                memset(cnt,0,sizeof cnt);
                queue<PII>q;
                q.push({1,0});
                dist[1]=0;
                cnt[1]=1;

                while(q.size())
                {
                    auto temp=q.front();
                    q.pop();
                    for(int i=h[temp.first];~i;i=ne[i])
                    {
                        int j=e[i];
                        if(cnt[j]>=2) continue;
                        int c=temp.second+1;
                        if(c!=dist[j])
                        {
                            cnt[j]++;
                            q.push({j,c});
                            if(j==n && cnt[j]==2) ans=c;
                        }
                        dist[j]=c;
                    }
                }
            }



    int get(int ans,int time,int change)
    {
        int sum=0;
        for(int i=0;i<ans;i++)
        {
            if((sum/change)&1)
            {
                sum=sum/change*change+change;
            }
            sum+=time;
        }
        return sum;
    }

    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {

        memset(h,-1,sizeof h);
        for(auto temp:edges)
        {
            add(temp[0],temp[1]);
            add(temp[1],temp[0]);
        }
        bfs(n);
        
        ans=get(ans,time,change);

        return ans;
    }
};
